package com.leetcode;

public class BinaryTreeMaxPathSum {
	public int maxPathSum(TreeNode root) {
		return calc(root).path;
	}
	
	private Score calc(TreeNode root) {
		if (root == null) return new Score(Integer.MIN_VALUE, 0);
		Score left = calc(root.left);
		Score right = calc(root.right);
		int maxSeg = maxs(0, root.val, root.val + left.seg, root.val + right.seg);
		int maxPath = maxs(left.path, right.path, root.val + left.seg + right.seg);
		return new Score(maxPath, maxSeg);
	}
	
	private int maxs(int... a) {
		int max = a[0];
		for (int i=1; i<a.length; i++) if (a[i] > max) max = a[i];
		return max;
	}
	
	private class Score {
		int path;
		int seg;
		public Score(int path, int seg) {
			this.path = path;
			this.seg = seg;
		}
	}
	
	private class TreeNode {
		TreeNode left;
		TreeNode right;
		int val;
		public TreeNode(int val) {
			this.val = val;
		}
	}
}
